#include <vector>
#include <set>
#include <algorithm>

using namespace std;

//效率低
// class Solution {
// public:
//     vector<vector<int>> threeSum(vector<int>& nums) {

//         int num1 = 0;
//         int num2 = 1;
//         int num3 = 2;

//         set<vector<int>> us;
//         while(num1<=nums.size()-3)
//         {

//             int sum = nums[num1]+nums[num2]+nums[num3];
//             if(sum == 0)
//             {
//                 vector<int> tmp;
//                 tmp.push_back(nums[num1]);
//                 tmp.push_back(nums[num2]);
//                 tmp.push_back(nums[num3]);
//                 sort(tmp.begin(),tmp.end());
//                 us.insert(tmp);
//             }
//             num3++;
//             if(num3==nums.size())
//             {
//                 num2++;
//                 if(num2 == nums.size()-1)
//                 {
//                     num1++;
//                     if(num1 == nums.size()-2)
//                         break;
//                     num2 = num1+1;
//                 }
//                 num3 = num2+1;
//             }

//         }
        
//         vector<vector<int>> ret;
//         for(auto& e:us)
//         {
//             ret.push_back(e);
//         }

//         return ret;

//     }
// };


//优化版本
// 1。数组排序预处理：先对输入数组 nums 进行排序，排序的目的有两个 一是让数组具备 “左小右大” 的有序性
// 为后续双指针灵活调整提供基础；二是让相同元素相邻排列 方便后续 set 自动过滤重复三元组 

// 2.固定三元组的首元素：通过 for 循环遍历数组 循环变量 i 从 0 开始 终止条件是 i <n-2（n 为数组长度）
// 确保 i 后面至少有两个元素能组成三元组 即首元素固定为 nums [i] 

// 3.用双指针查找三元组的后两个元素 对于每个固定的首元素 nums [i] 定义两个指针 left 指针初始位置为 i+1（即首元素右侧的第一个元素） 
// right 指针初始位置为 n-1（即数组的最后一个元素） 通过 while 循环（循环条件为 left < right）来遍历可能的后两个元素组合 
// 根据三数之和与 0 的关系调整指针位置 
// 若三数之和大于 0 说明当前组合数值偏大 将 right 指针左移一位（--right） 
// 若三数之和小于 0 说明当前组合数值偏小 将 left 指针右移一位（++left） 
// 若三数之和等于 0 说明找到有效三元组 将该三元组插入 set 集合 然后同时移动 left 和 right 指针（++left --right） 继续寻找其他可能的有效组合

// 4.实现去重并转换结果格式 利用 set 集合的特性自动去重 ——set 不允许存储重复元素 
// 相同的三元组会被自动过滤 无需手动编写去重逻辑 最后 将 set 集合中的元素转换为题目要求的 vector<vector<int>> 类型 直接返回该结果即可
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        set<vector<int>> ans; 
        for(int i = 0; i < n-2; ++i) 
        {
            int left = i+1, right = n-1;
            while(left < right) 
            {
                if(nums[i] + nums[left] + nums[right] > 0)
                {
                    --right;
                } 
                else if(nums[i] + nums[left] + nums[right] < 0) 
                {
                    ++left;
                } 
                else 
                {
                    ans.insert({nums[i], nums[left], nums[right]});
                    ++left;
                    --right;
                }
            }
        }
        return vector<vector<int>>(ans.begin(), ans.end());
    }
};